package com.sh.sort;

import java.util.Arrays;

/**
 * @ClassName InsertSort
 * @Description TODO
 * @Author yaoqiang
 * @Date 2020/11/8 10:12
 * @Version 1.0
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr={101,34,119,1};
        insertSort2(arr);
    }

    private static void insertSort2(int[] arr) {
        int insertVal=0;
        int insertIndex=0;
        //
        for (int i=1;i<arr.length;i++){
            //
            insertVal=arr[i];//把当前循环拿到的值。也就是要拿着和前面比对的值存到insertVal
            insertIndex=i-1;//这个比对值的下标

            while (insertIndex>=0&& insertVal<arr[insertIndex]){
                arr[insertIndex+1]=arr[insertIndex];
                insertIndex--;
            }
            if (insertIndex+1!=i){
                arr[insertIndex+1]=insertVal;
            }
            System.out.println(Arrays.toString(arr));
        }
    }

    private static void insertSort(int[] arr) {
        int insertVal=0;
        int insertIndex=0;
        for (int i=1;i<arr.length;i++){
            insertVal=arr[i];
            insertIndex=i-1;
            while (insertIndex>=0&& insertVal<arr[insertIndex]){
                arr[insertIndex+1]=arr[insertIndex];
                insertIndex--;
            }
            if (insertIndex+1!=i){
                arr[insertIndex+1]=insertVal;
            }
            System.out.println(Arrays.toString(arr));
        }
    }
}
